LCS3Strings.java

packagesection19_DynamicProgramming;

publicclassLCS3Strings {

publicstaticvoidmain(String[] args) {

// String s1 = "abcgd", s2 = "bcgad", s3 = "ad"; // 2
Strings1 = "abcd", s2 = "agcfd", s3 = "ad"; // 2
// String s1 = "geeks", s2 = "geeksfor", s3 = "geeksforgeeks"; // 5
// String s1 = "abc", s2 = "agcfd", s3 = "aeg"; // 1
// String s1 = "abcausdhbvaauhdpqweasdgd", s2 = "qwaeohfdasasdfqpaew", s3 = "bnprsdhfasoihqd"; // 2
// String s1 = "abeti", s2 = "btje", s3 = "tjjabt";

System.out.println(lcs3StrRecursion(s1, s2, s3, 0, 0, 0));

// top down
int[][][] storage = newint[s1.length()][s2.length()][s3.length()];
// proper initializing storage
for (inti = 0; i < storage.length; i++) {
for (intj = 0; j < storage[i].length; j++) {
for (intk = 0; k < storage[i][j].length; k++) {
storage[i][j][k] = -1;
 }
 }
 }

System.out.println(lcs3StrTopDownDP(s1, s2, s3, 0, 0, 0, storage));
// bottom up
System.out.println(lcs3StrBottomUpDP(s1, s2, s3));
 }

publicstaticintlcs3StrRecursion(Strings1, Strings2, Strings3, intvidx1, intvidx2, intvidx3) {

if (vidx1 == s1.length() || vidx2 == s2.length() || vidx3 == s3.length()) {
return0;
 }
charch1 = s1.charAt(vidx1);
charch2 = s2.charAt(vidx2);
charch3 = s3.charAt(vidx3);

intlcsLen = 0;
if (ch1 == ch2 && ch2 == ch3) {
lcsLen = 1 + lcs3StrRecursion(s1, s2, s3, vidx1 + 1, vidx2 + 1, vidx3 + 1);
 } else {
intoption1 = lcs3StrRecursion(s1, s2, s3, vidx1 + 1, vidx2, vidx3);
intoption2 = lcs3StrRecursion(s1, s2, s3, vidx1, vidx2 + 1, vidx3);
intoption3 = lcs3StrRecursion(s1, s2, s3, vidx1, vidx2, vidx3 + 1);

lcsLen = Math.max(option1, Math.max(option2, option3));
 }

returnlcsLen;
 }

publicstaticintlcs3StrTopDownDP(Strings1, Strings2, Strings3, intvidx1, intvidx2, intvidx3,
int[][][] storage) {

if (vidx1 == s1.length() || vidx2 == s2.length() || vidx3 == s3.length()) {
return0;
 }

if (storage[vidx1][vidx2][vidx3] != -1) {
returnstorage[vidx1][vidx2][vidx3];
 }
charch1 = s1.charAt(vidx1);
charch2 = s2.charAt(vidx2);
charch3 = s3.charAt(vidx3);

intlcsLen = 0;
if (ch1 == ch2 && ch2 == ch3) {
lcsLen = 1 + lcs3StrTopDownDP(s1, s2, s3, vidx1 + 1, vidx2 + 1, vidx3 + 1, storage);
 } else {
intoption1 = lcs3StrTopDownDP(s1, s2, s3, vidx1 + 1, vidx2, vidx3, storage);
intoption2 = lcs3StrTopDownDP(s1, s2, s3, vidx1, vidx2 + 1, vidx3, storage);
intoption3 = lcs3StrTopDownDP(s1, s2, s3, vidx1, vidx2, vidx3 + 1, storage);

lcsLen = Math.max(option1, Math.max(option2, option3));
 }

storage[vidx1][vidx2][vidx3] = lcsLen;

returnlcsLen;
 }

publicstaticintlcs3StrBottomUpDP(Strings1, Strings2, Strings3) {
intone = s1.length(), two = s2.length(), three = s3.length();
int[][][] storage = newint[one + 1][two + 1][three + 1];

for (intblock = one - 1; block >= 0; block--) {

for (introw = two - 1; row >= 0; row--) {

for (intcol = three - 1; col >= 0; col--) {

// logic from top down
charch1 = s1.charAt(block);
charch2 = s2.charAt(row);
charch3 = s3.charAt(col);

intlcsLen = 0;
if (ch1 == ch2 && ch2 == ch3) {
lcsLen = 1 + storage[block + 1][row + 1][col + 1];
 } else {
intoption1 = storage[block + 1][row][col];
intoption2 = storage[block][row + 1][col];
intoption3 = storage[block][row][col + 1];

lcsLen = Math.max(option1, Math.max(option2, option3));
 }

storage[block][row][col] = lcsLen;
 }
 }
 }
returnstorage[0][0][0];
 }
}